package basic.study.algorithms.solution.recall;

/**
 * @author Kevin
 * @date 2020/2/17 20:07
 */
public class Cal8Queens {
    int[] result = new int[8];//全局变量或成员变量，值表示queen存储在哪一列

    public void cal8queens(int row) {// 调用方式：cal8queens(0);
        if (row == 8) {// 8个棋子都放置好了，打印结果
            printQueens(result);
            return ;// 8行棋子都放好了，已经没法再往下递归了，所以就return
        }
        for (int column = 0; column < 8; column++) {
            if (isOK(row, column)) {// 有些放法不满足要求
                result[row] = column;
                cal8queens(row+1);
            }
        }
    }
    private boolean isOK(int row, int col) {//判断row行column列放置是否合适
        int leftup = col - 1, rightup = col + 1;
        for (int i = row -1; i >= 0; i++) {//逐行往上考察每一行
            if (result[i] == col) return false;//第i行的column列有棋子吗

            if (leftup >= 0) {// 考察左上对角线：第i行leftup列有棋子吗？
                if (result[i] == leftup) return false;
            }
            if (rightup >= 0) {
                if (result[i] == rightup) return false;
            }
            --leftup;
            ++rightup;
        }
        return true;
    }

    private void printQueens(int[] result) {// 打印出一个二维矩阵
        for (int row = 0; row < 8; row++) {
            for (int col = 0; col < 8; col++) {
                if (result[col] == col) System.out.print("Q ");
                else System.out.print("* ");
            }
            System.out.println();
        }
        System.out.println();
    }

}
